from mode import *
from mode import collections
import sys

class TreeNode:
    def __init__(self, x, num):
        self.sum = 0
        self.num = num
        self.val = x
        self.left = None
        self.right = None

def PrintTreeSum(root):
    if root is None:
        sys.stdout.write("{}")
        return
    sys.stdout.write("该树为{")
    v = [root]
    c = 0
    none = ""
    while c < len(v):
        if c == 0:
            sys.stdout.write("%d" % v[c].sum)
            v.append(v[c].left)
            v.append(v[c].right)
        else:
            if v[c] is None:
                none = none + ",null"
            else:
                sys.stdout.write("%s,%d" % (none, v[c].sum))
                none = ""
                v.append(v[c].left)
                v.append(v[c].right)
        c = c + 1
    sys.stdout.write("}")
    print()
    print('------------------------------------------------')



class Solution1:
    def maxValue(self, root: TreeNode):
        def preOrder(node):
            if not node:
                return
            preOrder(node.left)
            preOrder(node.right)
            node.sum += node.val
            if node.left:
                node.sum += node.left.sum
            if node.right:
                node.sum += node.right.sum

        def recur(node):
            deque = collections.deque()
            deque.append(node)
            maxValue = 0
            diffValue = 0
            targetNode = None
            while deque:
                size = len(deque)
                for i in range(size):
                    node = deque.popleft()
                    if node.left:
                        diffValue = abs(node.sum - 2 * node.left.sum)
                        if maxValue < diffValue:
                            maxValue = diffValue
                            targetNode = node.left
                    if node.right:
                        diffValue = abs(node.sum - 2 * node.right.sum)
                        if maxValue < diffValue:
                            maxValue = diffValue
                            targetNode = node.right
            return targetNode

        preOrder(root)
        PrintTree(root)
        PrintTreeSum(root)
        targetNode = recur(root)
        return targetNode.num

def genetateTree():
    nums = [4, 9, 7, 8]
    treeList = [[0, 1], [0, 3], [1, 2]]
    hashMap = {}
    for i in range(len(nums)):
        node = TreeNode(nums[i], i)
        hashMap[i] = node
    for i, j in treeList:
        nodeFather = hashMap[i]
        nodeChild = hashMap[j]
        if not nodeFather.left:
            nodeFather.left = nodeChild
        else:
            nodeFather.right = nodeChild

    PrintTree(hashMap[0])



if __name__ == "__main__":
    """
                  4
             9         -8
        -7       
    """

    n = TreeNode(4, 0)
    n1 = TreeNode(9, 1)
    n2 = TreeNode(int('-8'), 3)
    n3 = TreeNode(int('-7'), 2)
    n.left = n1
    n.right = n2
    n1.left = n3
    PrintTree(n)

    # print(Solution().maxValue(n))
    print(Solution1().maxValue(n))

    # genetateTree()
    # genetateTree1()
